package io.zhengsh.vvip.leetcode.bfs;

import java.util.LinkedList;
import java.util.Queue;

public class Q1091_ShortestPathBinaryMatrix {

    class Solution {
        int[] dx = new int[]{0, 1, 1, 1, 0, -1, -1, -1};  // 行变化量
        int[] dy = new int[]{1, 1, 0, -1, -1, -1, 0, 1};  // 列变化量

        public int shortestPathBinaryMatrix(int[][] grid) {
            int m = grid.length; // 行数
            int n = grid[0].length; // 列数

            if (grid[0][0] == 1) {
                return -1;
            }

            Queue<int[]> q = new LinkedList<>();
            q.offer(new int[]{0, 0, 1});

            grid[0][0] = 1;
            while (!q.isEmpty()) { // 如果不为空
                int[] temp = q.poll();
                if (temp[0] == m - 1 & temp[1] == n - 1) { // 如果是终点就返回
                    return temp[2];
                }
                for (int t = 0; t < 8; t++) { //四周扩散
                    int x = temp[0] + dx[t];
                    int y = temp[1] + dy[t];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0) {
                        q.offer(new int[]{x, y, temp[2] + 1}); // 如果扩散到达的点的值为 0
                        grid[x][y] = 1;
                    }
                }
            }
            return -1; // 如果没有到达中终点, 就返回 -1
        }
    }
}
